#pragma once

#include <iostream>
#include <ctime>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>

class Sort{
  private:
    Sort(){}
    //Sort(const Sort&){}
    Sort(const Sort& tmp) = delete;

  public:
  static void Print(const std::vector<int>& array)
  {
    for(auto& e : array){
      std::cout << e << " ";
    }
    std::cout << std::endl;
  }

    static void SelectSort(std::vector<int>& array)
    {
      assert(array.size());
      int left = 0;
      int right = array.size() - 1;
      
      while(left < right){
        int max = left;
        int min = left;
        for(int i = left; i <= right; i++){
          if(array[i] > array[max]){
              max = i;
          }
          if(array[i] < array[min]){
              min= i;
          }
        }

        std::swap(array[left], array[min]);
        if(left == max) max = min;
        std::swap(array[right], array[max]);

        left++;right--;
      }
    }
    static void InsertSort(std::vector<int>& array)
    {
      assert(array.size());
      for(int i = 0; i < (int)array.size() - 1; i++){
        int end = i;
        while(end >= 0){
          if(array[end + 1] < array[end]){
            std::swap(array[end + 1], array[end]);
            end--;
          }
          else break;
        }
      }
    //int left = 1;
    //while(left < (int)array.size()){
    //  for(int i = left - 1; i >= 0; i--){
    //    if(array[left] < array[i]) {
    //      std::swap(array[left], array[i]);
    //      left = i;
    //    }
    //  }
    //  left++;
    //}
    }
    static void BubbleSort(std::vector<int>& array)
    {
      assert(array.size());
      int left = 0;
      int right = array.size();
      while(left < right){
        for(int j = left; j < right; j++){
          if(array[j] > array[j + 1]){
            std::swap(array[j], array[j + 1]);
          }
        }
        right--;
      }
    }
  private:
    static void AdjustDown(std::vector<int>& array, int father, int end)
    {
      int child = (father << 1) + 1;
      while(child < end){
        if(child + 1 < end && array[child] < array[child + 1]){
          child++;
        }
        if(array[father] < array[child]){
          std::swap(array[child], array[father]);
        }
        else break;

        father = child;
        child = (child << 1) + 1;
      }
    }
    static void AdjustUP(std::vector<int>& array, int child)
    {
      int father = (child - 1) >> 1;
      while(child > 0){
        if(array[father] < array[child]){
          std::swap(array[father], array[child]);
        }
        else break;

        child = father;
        father = (father - 1) >> 1;
      }
    }
  public:
    static void HeapSort(std::vector<int>& array)
    {
      assert(array.size());
      //for(int i = 1; i < (int)array.size(); i++){
      //  AdjustUP(array, i);
      //}
      //int father = (array.size() >> 1) - 1;
      int father = (array.size() - 1) >> 1;
      for(int i = father; i >= 0; i--){
        AdjustDown(array, i, (int)array.size());
      }

      for(int i = 0; i < (int)array.size(); i++){
        AdjustDown(array, 0, (int)array.size() - i);
        std::swap(array[0], array[array.size() - i - 1]);
      }
    }
    static void ShellSort(std::vector<int>& array)
    {
      assert(array.size()); 
      int gap = array.size();
      while(gap > 1){
        gap = gap / 3 + 1;
        for(int i = 0; i < (int)array.size() - gap; i++){
          int end = i;
          while(end >= 0){
            if(array[end + gap] < array[end]){
              std::swap(array[end + gap], array[end]);
            }
            else break;
            end -= gap;
          }
        }
      }
    }
  private:
    //三数取中
    static int GetMidIndex(std::vector<int>& array, int left, int right, int mid)
    {
      int midIndex = mid;
      if(array[mid] > array[left]){
        if(array[mid] > array[right])
          if(array[left] > array[right])
            midIndex = right;
          else 
            midIndex = left;
      }
      else{
        if(array[mid] < array[right])
          if(array[left] < array[right])
            midIndex = left;
          else
            midIndex = right;
      }

      return midIndex;
    }
    //内置递归快排
    static void _RQueickSort(std::vector<int>& array, int left, int right)
    {
      //需要>=防止发生段错误
      if(left >= right)
        return ;
      
      int meeti = PartOne(array, left, right);
      //int meeti = PartTwo(array, left, right);
      //int meeti = PartThree(array, left, right);

      _RQueickSort(array, left, meeti - 1);
      _RQueickSort(array, meeti + 1, right);
    }
    //左右指针法
    static int PartOne(std::vector<int>& array, int left, int right)
    {
      int mid = GetMidIndex(array, left, right, (left + right) >> 1);
      std::swap(array[mid], array[left]);

      int keyi = left;
      int begin = left;
      int end = right;
      while(left <= right){
        while(begin < end && array[keyi] <= array[end]) end--;
        while(begin < end && array[keyi] >= array[begin]) begin++;
        if(begin < end) std::swap(array[begin], array[end]);
        else {
          std::swap(array[keyi], array[begin]);
          break;
        }
      }

      return begin;
    }
    //挖坑法
    static int PartTwo(std::vector<int>& array, int left, int right)
    {
      int mid = GetMidIndex(array, left, right, (left + right) >> 1); 
      std::swap(array[mid], array[left]);

      int key = array[left];
      while(left < right){
        while(left < right && array[right] >= key) right--;
        array[left] = array[right];

        while(left < right && array[left] <= key) left++;
        array[right] = array[left];

        if(left == right) {
          array[left] = key;
          break;
        }
      }

      return left;
    }
    //前后指针法
    static int PartThree(std::vector<int>& array, int left, int right)
    {
      int mid = GetMidIndex(array, left, right, (left + right) >> 1);
      std::swap(array[mid], array[right]);
      int cur = left;
      int prev = left - 1;
      int keyi = right;
      while(cur <= right){
        if(array[cur] <= array[keyi] && ++prev != cur){
          std::swap(array[cur], array[prev]);
        }
        cur++;
      }
      //while(cur <= right){
      //  if(array[cur] < array[keyi] && ++prev != cur) {
      //    std::swap(array[cur], array[prev]);
      //  }
      //  if(cur == right){
      //    std::swap(array[++prev], array[keyi]);
      //  }
      //  cur++;
      //}

      //int mid = GetMidIndex(array, left, right, (left + right) >> 1);
      //std::swap(array[mid], array[left]);

      //int keyi = left;
      //int cur = left + 1;
      //int prev = left;

      //while(cur <= right){
      //  if(array[cur] < array[keyi] && ++prev != cur){
      //    std::swap(array[cur], array[prev]);
      //  }
      //  cur++;
      //}
      //std::swap(array[keyi], array[prev]);
      //while(cur <= right){
      //  while(cur <= right && array[cur] > array[keyi]) cur++;
      //  if(cur <= right) {
      //    std::swap(array[++prev], array[cur++]);
      //  }
      //  if(cur > right) {
      //    std::swap(array[prev], array[keyi]);
      //  }
      //}
      return prev;
    }
  public:
    // 递归快排
    static void RQuickSort(std::vector<int>& array)
    {
      assert(array.size());
      _RQueickSort(array, 0, (int)array.size() - 1); 
    }
  private:
    //用栈实现非递归
    static void _NoRStackQuickSort(std::vector<int>& array, int left, int right)
    {
      std::stack<int> st;
      st.push(left); 
      st.push(right);

      while(st.size()){
        int end = st.top();st.pop();
        int begin = st.top();st.pop();

        int meeti = PartThree(array, begin, end);

        if(begin < meeti - 1){
          st.push(begin);
          st.push(meeti - 1);
        }

        if(meeti + 1 < end){
          st.push(meeti + 1);
          st.push(end);
        }
      }
    }
    //用队列实现非递归
    static void _NoRQueueQuickSort(std::vector<int>& array, int left, int right)
    {
      std::queue<int> q;
      q.push(left);
      q.push(right);

      while(q.size()){
        int begin = q.front(); q.pop();
        int end = q.front(); q.pop();

        int meeti = PartThree(array, begin, end);

        if(begin < meeti - 1){
          q.push(begin);
          q.push(meeti - 1);
        }

        if(meeti + 1 < end){
          q.push(meeti + 1);
          q.push(end);
        }
      }
    }
  public:
    // 非递归快排
    static void NoRQuickSort(std::vector<int>& array)
    {
      assert(array.size());
      
      //_NoRStackQuickSort(array, 0, array.size() - 1);
      _NoRQueueQuickSort(array, 0, array.size() - 1);
    }
  private:
    static void _RMergeSort(std::vector<int>& array, int left, int right, std::vector<int>& tmp)
    {
      if(left == right) return ;

      int mid = (left + right) >> 1;
      _RMergeSort(array, left, mid, tmp);
      _RMergeSort(array, mid + 1, right, tmp);

      int first = left;
      int second = mid + 1;
      int cur = first;
      while(first <= mid && second <= right)
      {
        //建议使用<=，可以保证稳定性
        if(array[first] <= array[second]){
          tmp[cur++] = array[first++];
        }
        else{
          tmp[cur++] = array[second++];
        }
      }

      while(first <= mid){
        tmp[cur++] = array[first++];
      }

      while(second <= right){
        tmp[cur++] = array[second++];
      }

      //拷贝归并的数据
      for(int i = left; i <= right; i++){
        array[i] = tmp[i];
      }
    }
  public:
    static void RMergeSort(std::vector<int>& array)
    {
     assert(array.size()); 

     std::vector<int> tmp(array.begin(), array.end());
     _RMergeSort(array, 0, array.size() - 1, tmp);
    }
    static void NoRMergeSort(std::vector<int>& array)
    {
      assert(array.size());

      std::vector<int> tmp(array.begin(), array.end());
      int gap = 1;
      while(gap < (int)array.size() + 1){
        int cur = 0; 
        for(int i = 0; i < (int)array.size(); i += 2 * gap){
          int first = i;
          int firstEnd = i + gap - 1;
          int second = i + gap;
          int secondEnd = i + 2 * gap - 1;
          
          //调整区间
          if(firstEnd >= (int)array.size()){
            firstEnd = array.size() - 1;
            second = (int)array.size();
            secondEnd = (int)array.size() - 1;
          } 
          else if(secondEnd >= (int)array.size()) secondEnd = array.size() - 1;
          
          while(first <= firstEnd && second <= secondEnd){
            if(tmp[first] < tmp[second]) array[cur++] = tmp[first++];
            else array[cur++] = tmp[second++];
          }

          while(first <= firstEnd) array[cur++] = tmp[first++];
          while(second <= secondEnd) array[cur++] = tmp[second++];
        }
        gap *= 2;
        tmp = array;
      }
    }
};
